
dojo.provide("dojo.collections.SkipList");dojo.require("dojo.collections.Collections");dojo.require("dojo.experimental");dojo.experimental("dojo.collections.SkipList");dojo.collections.SkipList=function(){function node(height,val){this.value=val;this.height=height;this.nodes=new nodeList(height);this.compare=function(val){if(this.value>val){return 1;}
if(this.value<val){return-1;}
return 0;};this.incrementHeight=function(){this.nodes.incrementHeight();this.height++;};this.decrementHeight=function(){this.nodes.decrementHeight();this.height--;};}
function nodeList(height){var arr=[];this.height=height;for(var i=0;i<height;i++){arr[i]=null;}
this.item=function(i){return arr[i];};this.incrementHeight=function(){this.height++;arr[this.height]=null;};this.decrementHeight=function(){arr.splice(arr.length-1,1);this.height--;};}
function iterator(list){this.element=list.head;this.atEnd=function(){return(this.element==null);};this.get=function(){if(this.atEnd()){return null;}
this.element=this.element.nodes[0];return this.element;};this.reset=function(){this.element=list.head;};}
function chooseRandomHeight(max){var level=1;while(Math.random()<PROB&&level<max){level++;}
return level;}
var PROB=0.5;var comparisons=0;this.head=new node(1);this.count=0;this.add=function(val){var updates=[];var current=this.head;for(var i=this.head.height;i>=0;i--){if(!(current.nodes[i]!=null&&current.nodes[i].compare(val)<0)){comparisons++;}
while(current.nodes[i]!=null&&current.nodes[i].compare(val)<0){current=current.nodes[i];comparisons++;}
updates[i]=current;}
if(current.nodes[0]!=null&&current.nodes[0].compare(val)==0){return;}
var n=new node(val,chooseRandomHeight(this.head.height+1));this.count++;if(n.height>this.head.height){this.head.incrementHeight();this.head.nodes[this.head.height-1]=n;}
for(i=0;i<n.height;i++){if(i<updates.length){n.nodes[i]=updates[i].nodes[i];updates[i].nodes[i]=n;}}};this.contains=function(val){var current=this.head;var i;for(i=this.head.height-1;i>=0;i--){while(current.item(i)!=null){comparisons++;var result=current.nodes[i].compare(val);if(result==0){return true;}else{if(result<0){current=current.nodes[i];}else{break;}}}}
return false;};this.getIterator=function(){return new iterator(this);};this.remove=function(val){var updates=[];var current=this.head;for(var i=this.head.height-1;i>=0;i--){if(!(current.nodes[i]!=null&&current.nodes[i].compare(val)<0)){comparisons++;}
while(current.nodes[i]!=null&&current.nodes[i].compare(val)<0){current=current.nodes[i];comparisons++;}
updates[i]=current;}
current=current.nodes[0];if(current!=null&&current.compare(val)==0){this.count--;for(var i=0;i<this.head.height;i++){if(updates[i].nodes[i]!=current){break;}else{updates[i].nodes[i]=current.nodes[i];}}
if(this.head.nodes[this.head.height-1]==null){this.head.decrementHeight();}}};this.resetComparisons=function(){comparisons=0;};};